1. Field of the Invention
This invention relates, in general, to pictorial communications and, more specifically, to apparatus and methods for converting gray-scale pixel information into binary printing data.
2. Description of the Prior Art
Various types of printing or rendering systems are used to reproduce an image on a viewable medium, such as a sheet of paper. Typically, the rendering device produces a large number of pixels or dots which, when viewed at a normal distance without magnification, produce the desired image. Using gray-scale or gray-level dot renderings increases the ability of the rendered image to closely match the desired image, which may be a copy of a continuous tone picture being produced on a copy machine having an electronic scanner. However, true gray-level rendering requires special types of apparatus and demands a large amount of memory for high quality outputs, especially when color is being used.
Several techniques have been used according to the prior art to produce information which has gray-level content on apparatus which is not capable of printing true gray-levels. While not all encompassing of the methods available, error diffusion and halftoning are frequently used when it is desired to render perceivable levels of gray by a rendering device which can only produce dots having two levels, such as a binary printer. With error diffusion, the dots are rendered based upon a thresholding process which changes the corresponding pixel data depending upon what happened in a previous thresholding process. If the error-corrected pixel data is above the threshold, it is printed in one of the binary levels, such as full black. If the pixel data is below the threshold, it is printed in the other binary level, or white (no print). The density difference between the binary dot and the gray-level pixel data is considered an error since the dot is usually not exactly the same gray-level as the original pixel. This error is propagated to subsequent pixel-dot comparisons to alter those comparisons either by changing the gray-level pixel data or the threshold level. By using this technique, a better rendering of the gray-levels in the pixel information can be made than could be accomplished by simply thresholding on a one-to-one basis for each pixel and rendered dot.
Halftoning uses the perceivable gray-level produced by several rendered dots grouped together in a cell. Normally, the individual dots have only two levels of density. The overall gray-level of the cell is near to the gray-level for the corresponding pixel in the input information. This approach uses binary dots to form the gray-levels, but the resolution of the rendered image can suffer unless more dots can be rendered for each pixel of data. In any event, such a system requires a considerable amount of image processing and a relatively high resolution rendering device to produce high quality images.
Some techniques use a combination of both systems to achieve the desired result. U.S. Pat. No. 4,680,645, issued on July 14, 1987, discloses a system whereby gray-level dots are effectively produced by varying the size of the dots. Large dots are used when the density of the pixel is high. When the density is low, small dots are rendered. In this patent, the number of discrete gray-levels which can be produced by the dots is less than the number of gray-levels included in the original pixel information. Therefore, a type of error diffusion is used to determine the size of subsequent dots. This patent also recognizes that adjacent dots may overlap when they are rendered at or near to the maximum size. However, the error diffusion method disclosed therein does not prevent this nonlinearity, although the patent indicates that performing the calculations in optical density units, which are more observer related, will yield better images devoid of nonlinear artifacts. See column 2, line 65to column 3, line 16, of the patent.
U.S. Pat. No. 4,654,721, issued on Mar. 31, 1987, discloses a system whereby halftone cells are created based upon the gray-level of the corresponding pixel in the data. When the gray-level represented by the halftone cell is different from the gray-level pixel value, an error is propagated or diffused to at least two other halftone cells. The basic method of rendering disclosed in this patent does not present itself with the problems associated with overlapping dots which the present invention recognizes and solves.
An important problem with rendering devices which can produce dots which are overlapping other dots is that conventional error diffusion techniques assume that the dots do not overlap. In determining the amount of error which will influence the thresholding operation of an adjacent dot, no consideration is given to the fact that the dots may overlap in conventional error diffusion. For example, in the case where two adjacent dots overlap by 20 percent of their area, the resulting error diffused from one dot to the other dot can be incorrect by as much as 20 percent, depending upon the binary level rendered for the dots.
Therefore, it is desirable, and it is an object of this invention, to provide a method and apparatus for converting gray-level pixel information into binary printing data which compensates for the overlap between adjacent dots rendered on the output medium.